package pers.qianyu.month_202012.date_20201229;

import org.junit.*;

import java.util.*;
import java.util.stream.*;

/**
 * 120. 三角形最小路径和
 * https://leetcode-cn.com/problems/triangle/
 *
 * @author mizzle rain
 * @date 2020-12-29 22:07
 */
public class MinimumTotal {
    public int minimumTotal1(List<List<Integer>> triangle) {
        int size = triangle.size();
        if (size == 0) {
            return 0;
        }
        int width = triangle.get(size - 1).size();
        int[][] dp = new int[size][width];
        dp[0][0] = triangle.get(0).get(0);
        for (int i = 1; i < size; i++) {
            for (int j = 0; j <= i; j++) {
                int curValue = triangle.get(i).get(j);
                if (j == 0) {
                    dp[i][j] = dp[i - 1][0] + curValue;
                } else if (j == i) {
                    dp[i][j] = dp[i - 1][j - 1] + curValue;
                } else {
                    dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i - 1][j]) + curValue;
                }
            }
        }
        //Arrays.stream(dp).forEach(i -> System.out.println(Arrays.toString(i)));
        int min = Integer.MAX_VALUE;
        for (int i : dp[size - 1]) {
            min = Integer.min(min, i);
        }
        return min;
    }

    // 滚动数组优化
    public int minimumTotal2(List<List<Integer>> triangle) {
        int size = triangle.size();
        if (size == 0) {
            return 0;
        }
        int width = triangle.get(size - 1).size();
        int[] dp = new int[width];
        dp[0] = triangle.get(0).get(0);
        for (int i = 1; i < size; i++) {
            for (int j = i; j >= 0; j--) {
                int curValue = triangle.get(i).get(j);
                if (j == 0) {
                    dp[j] = dp[0] + curValue;
                } else if (j == i) {
                    dp[j] = dp[j - 1] + curValue;
                } else {
                    dp[j] = Math.min(dp[j - 1], dp[j]) + curValue;
                }
            }
            //System.out.println(Arrays.toString(dp));
        }
        int min = Integer.MAX_VALUE;
        for (int i : dp) {
            min = Integer.min(min, i);
        }
        return min;
    }

    // 滚动数组优化 + 从后往前遍历优化
    public int minimumTotal(List<List<Integer>> triangle) {
        int size = triangle.size();
        if (size == 0) {
            return 0;
        }
        Integer[] dp = triangle.get(size - 1).toArray(new Integer[0]);
        for (int i = size - 2; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                dp[j] = Math.min(dp[j], dp[j + 1]) + triangle.get(i).get(j);
            }
        }
        return dp[0];
    }

    @Test
    public void test1() {
        List<List<Integer>> param = Stream.of(
                Stream.of(2).collect(Collectors.toList()),
                Stream.of(3, 4).collect(Collectors.toList()),
                Stream.of(6, 5, 7).collect(Collectors.toList()),
                Stream.of(4, 1, 8, 3).collect(Collectors.toList())
        ).collect(Collectors.toList());
        int result = new MinimumTotal().minimumTotal(param);
        Assert.assertEquals(result, 11);
    }

    @Test
    public void test2() {
        List<List<Integer>> param = Stream.of(
                Stream.of(2).collect(Collectors.toList()),
                Stream.of(3, 4).collect(Collectors.toList()),
                Stream.of(6, 5, 9).collect(Collectors.toList()),
                Stream.of(4, 4, 8, 0).collect(Collectors.toList())
        ).collect(Collectors.toList());
        int result = new MinimumTotal().minimumTotal(param);
        Assert.assertEquals(result, 14);
    }
}
